package string;

/**
 * O(n), find one longest palindromic substring
 * 
 * @author yinzichen
 * 
 */
public class Palindrome {
	static final char delim = '#';

	public String getLongestPalindrome(String text) {
		StringBuilder ext = new StringBuilder(text.length() * 2 + 1);
		ext.append(delim);
		for (int i = 0; i < text.length(); ++i) {
			ext.append(text.charAt(i));
			ext.append(delim);
		}
		int n = ext.length();
		int[] p = new int[n];
		int id = 0, mx, ctr = 0;
		for (int i = 1; i < n; ++i) {
			mx = p[id] + id;
			p[i] = mx > i ? Math.min(mx - i, p[id * 2 - i]) : 0;
			int upper = Math.min(i, n - i - 1);
			while (p[i] < upper
					&& ext.charAt(i + p[i] + 1) == ext.charAt(i - p[i] - 1))
				p[i]++;
			if (i + p[i] > mx) {
				mx = i + p[i];
				id = i;
			}
			if (p[i] > p[ctr]) {
				ctr = i;
			}
		}
		return text.substring((ctr - p[ctr]) / 2, (ctr + p[ctr]) / 2);
	}

}
